The present invention relates to apparatus and methods for facilitating data routing in a computer network. More specifically, it relates to handling stale or invalid Link State Packets (LSP's), which are used in a Link State Type Protocol, such as the IS-IS protocol.
In a network that uses the IS-IS protocol, each node generates a set of LSP's that describe its connectivity to its neighbors and floods these LSPs to its neighbors. This connectivity information specifies who is connected to whom and the cost associated with each connection, such as a value which is configured by an operator to correspond to a speed of a particular connection. Thus, each node receives connectivity information in the form of LSPs from its neighbors. The LSPs received at a particular node are then flooded by the particular node to its neighbors and, hence, propagated throughout the network. For example as shown in FIG. 1, a first Node A is connected to Nodes B, C, and D. Node A will send one or more LSPs to each of its neighbors B, C, and D, and the LSP(s) will specify that Node A is connected directly to Nodes B, C, and D. When Node C, who is connected to Node A and E, receives an LSP from Node A, Node C will then flood these LSP(s) to its neighbor Node E. Node C also sends its own LSPs specifying its particular connection information to its neighbor Node E and Node A. Each node in the network then uses its received LSPs to build a map of connectivity and determine possible routing paths (e.g., to form a routing table) based on the map of connectivity.
One concern in this type of protocol operation is reliability. It is important that each node acquires the most updated LSPs from its neighbor nodes. Towards this end, the IS-IS protocol utilizes built in sequence numbers to ensure that all nodes reliably acquire updated LSPs. When a particular node initially sends an LSP, the sent LSP includes a sequence number 1. Thereafter, when the particular node sends an updated LSP, the LSP will include an incremented sequence number. The process of determining which LSP is newer generally includes comparing the sequence number, remaining life time, and checksum of two LSP's. If the sequence number of one of the LSP's is higher, the LSP with the higher sequence number is newer. If the sequence numbers are the same, the LSP with zero remaining life time is considered newer. If both LSPs have zero remaining life time, the LSP with the higher checksum is considered newer.
The IS-IS Protocol also includes several security mechanisms. One security measure includes the use of a single password or key to authenticate each LSP. That is, each node in a particular network is configured to send its LSPs with a particular password and to authenticate received LSPs using the same particular password. Some implementations allow one to configure to send a password without checking the password for received packets, i.e., one-way authentication.
The use of a single key has several disadvantages. For instance, a person may leave a company and retain the password, as a result, compromising the security of the company's network. Another security approach includes multiple keys that are used sequentially for limited time periods. A first key is used during an initial time period and then replaced with a second key. The second key is then used for a second period of time until it too is replaced by a third key, etc.
Although the above type of Link State Protocol schemes work well under certain conditions, stale or invalid LSPs can be improperly handled by a receiving node and its neighbors' databases under other conditions. For instance, LSPs which contain updated connectivity information are sometimes not interpreted as being updated LSPs, and are instead discarded without updating the receiving nodes databases. In other situations, it may be desirable to isolate a node which is being attacked from the other nodes of a network. Effective mechanisms for isolating such an attacked node are currently unavailable.
Accordingly, improved mechanisms for updating and purging LSPs are needed. In particular, improved mechanisms for recognizing and handling updated LSPs, as well as improved mechanisms for purging stale and invalid LSPs, are needed.